import Node from "./Node";
import defaultEquals from "../utils/defaultEquals";

export interface LinkedListInterface<T> {
    // 构造函数


    // 实例属性
    head: Node<T> | undefined; // 保存头元素的引用
    count: number; // 总数量
    equals(a: T, b: T): boolean;

    // 实例方法
    push(element: T): void;  // 末尾追加一个元素
    insert(element: T, index: number): void;  // 在index处添加一个元素
    getElementAt(index: number): Node<T> | undefined; // 获取index处的元素
    getValueAt(index: number): T | undefined;

    remove(element: T): T | undefined; // 删除值为element的元素
    indexOf(element: T): number | undefined; // 获取值为element的元素的下标
    removeAt(index: number): T | undefined; // 删除下标为index的元素
    isEmpty(): boolean;  // 判断链表是否为空
    size(): number;  // 获取链表大小
    toString(): string;  // 链表输出格式化

}

export interface equalsType<T> {
    (a: T, b: T): boolean;
}


export default class LinkedList<T> implements LinkedListInterface<T> {
    count: number;
    head: Node<T> | undefined;

    constructor(equals: equalsType<T> = defaultEquals) {
        this.count = 0;
        this.head = undefined;
        this.equals = equals;
    }

    equals(a: T, b: T): boolean {
        return false;
    }

    // 获取指定下标的node实例
    getElementAt(index: number): Node<T> | undefined {
        if (index < 0) {
            return undefined;
        }

        if (index === 0) {
            return this.head;
        }
        if (index >= this.count) {
            return undefined;
        }
        let node = this.head;
        for (let i = 0; i < index; i++) {
            node = node?.next;
        }
        return node;
    }

    // 获取指定下标的node value
    getValueAt(index: number): T | undefined {
        return this.getElementAt(index)?.value
    }

    indexOf(element: T): number {
        let node = this.head;
        let i = 0;
        let flag = false;
        while (node) {
            if (this.equals(element, node.value)) {
                flag = true;
                break;
            }
            i++;
            node = node.next;
        }
        return flag ? i : -1;
    }

    insert(element: T, index: number): void {
        let new_node: Node<T> = new Node();
        new_node.value = element;
        if (index > this.count) {
            throw new Error("下标越界")
        }
        this.count++;
        let p_node: Node<T> | undefined = undefined;
        let n_node: Node<T> | undefined = undefined;

        if (index === 0) {
            new_node.next = this.head;
            this.head = new_node;
            return;
        }
        p_node = <Node<T>>this.getElementAt(index - 1);
        n_node = p_node.next;
        p_node.next = new_node;
        new_node.next = n_node;
    }

    isEmpty(): boolean {
        return this.count === 0;
    }

    push(element: T): void {
        let n_node = new Node<T>();
        n_node.value = element;
        if (this.isEmpty()) {
            this.count++;
            this.head = n_node;
            return;
        }
        let lastNode = <Node<T>>this.getElementAt(this.count - 1);
        this.count++;
        lastNode.next = n_node;
    }

    remove(element: T): T | undefined {
        const index = this.indexOf(element);
        if (index === -1) {
            return undefined;
        }
        return this.removeAt(index)
    }

    removeAt(index: number): T | undefined {
        if (this.isEmpty() || index >= this.count) {
            return undefined;
        }

        let now_node = this.getElementAt(index);
        let p_node = this.getElementAt(index - 1);
        let n_node = now_node?.next
        if (index === 0) {
            this.head = n_node;
        }
        if (p_node) {
            p_node.next = n_node;
        }
        this.count--;
        return now_node?.value;
    }

    size(): number {
        return this.count;
    }

    toString(): string {
        let str = "";
        let node = this.head
        while (node) {
            str += node.value;
            str += ",";
            node = node.next;
        }
        str = str.substr(0,   str.length - 1)
        return str;
    }
}
/*
let linkedList = new LinkedList<string>();
console.log("新建是否为空", linkedList.isEmpty());
console.log("新建大小", linkedList.size());

linkedList.push("1");
console.log("加入一个数据=================1")
console.log("查看当前是否为空", linkedList.isEmpty());
console.log("查看当前大小", linkedList.size());
console.log("获取第0个数据", linkedList.getValueAt(0));
console.log("获取第0个节点", linkedList.getElementAt(0));
console.log("查看数据", linkedList.toString())

linkedList.push("2");
console.log("加入二个数据=================2")
console.log("查看当前是否为空", linkedList.isEmpty());
console.log("查看当前大小", linkedList.size());
console.log("获取第1个数据", linkedList.getValueAt(1));
console.log("获取第1个节点", linkedList.getElementAt(1));
console.log("查看数据", linkedList.toString())

linkedList.insert("3",1);
console.log("插入第三个数据=================3")
console.log("查看当前是否为空", linkedList.isEmpty());
console.log("查看当前大小", linkedList.size());
console.log("获取第1个数据", linkedList.getValueAt(1));
console.log("获取第1个节点", linkedList.getElementAt(1));
console.log("查看数据", linkedList.toString());

linkedList.insert("4",linkedList.size());
console.log("插入第四个数据=================4")
console.log("查看当前是否为空", linkedList.isEmpty());
console.log("查看当前大小", linkedList.size());
console.log("获取第3个数据", linkedList.getValueAt(3));
console.log("获取第3个节点", linkedList.getElementAt(3));
console.log("查看数据", linkedList.toString());

console.log(linkedList.remove("2"));
console.log("删除数据=================2")
console.log("查看当前是否为空", linkedList.isEmpty());
console.log("查看当前大小", linkedList.size());
console.log("查看数据", linkedList.toString());

console.log(linkedList.removeAt(0));
console.log("删除数据下标=================0")
console.log("查看当前是否为空", linkedList.isEmpty());
console.log("查看当前大小", linkedList.size());
console.log("查看数据", linkedList.toString());

console.log(linkedList.removeAt(2));
console.log("删除数据下标=================2")
console.log("查看当前是否为空", linkedList.isEmpty());
console.log("查看当前大小", linkedList.size());
console.log("查看数据", linkedList.toString());

console.log(linkedList.removeAt(8));
console.log("删除数据=================越界")
console.log("查看当前是否为空", linkedList.isEmpty());
console.log("查看当前大小", linkedList.size());
console.log("查看数据", linkedList.toString());

console.log(linkedList.remove("啦啦啦"));
console.log("删除数据=================越界")
console.log("查看当前是否为空", linkedList.isEmpty());
console.log("查看当前大小", linkedList.size());
console.log("查看数据", linkedList.toString());
*/
